graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a Pfaffian orientation of an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

assigns a direction to each edge, so that certain cycles (the "even central cycles") have an odd number of edges in each direction. When a graph has a Pfaffian orientation, the orientation can be used to count the

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...

s of the graph. This is the main idea behind the

FKT algorithm The FKT algorithm, named after Fisher, Kasteleyn, and Temperley, counts the number of perfect matchings in a planar graph in polynomial time. This same task is #P-complete for general graphs. For matchings that are not required to be perfect, ...

for counting perfect matchings in

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

s, which always have Pfaffian orientations. More generally, every graph that does not have the

utility graph As a topic of economics, utility is used to model worth or value. Its usage has evolved significantly over time. The term was introduced initially as a measure of pleasure or happiness as part of the theory of utilitarianism by moral philosopher ...

K_

as a

graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...

has a Pfaffian orientation, but

K_

does not, nor do infinitely many other minimal non-Pfaffian graphs.

Definitions

A Pfaffian orientation of an

is an

orientation Orientation may refer to: Positioning in physical space * Map orientation, the relationship between directions on a map and compass directions * Orientation (housing), the position of a building with respect to the sun, a concept in building de ...

in which every even central cycle is oddly oriented. The terms of this definition have the following meanings: *An orientation is an assignment of a direction to each edge of the graph. *A cycle

C

is even if it contains an even number of edges. *A cycle

C

is central if the subgraph of

G

formed by removing all the vertices of

C

has a

; central cycles are also sometimes called alternating circuits. *Cycle

C

is oddly oriented if each of the two orientations of

C

is consistent with an odd number of edges in the orientation.

Application to counting matchings

Pfaffian orientations have been studied in connection with the

for counting the number of perfect matchings in a given graph. In this algorithm, the orientations of the edges are used to assign the values

\pm 1

to the variables in the

Tutte matrix In graph theory, the Tutte matrix ''A'' of a graph ''G'' = (''V'', ''E'') is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once. If the set of vert ...

of the graph. Then, the

Pfaffian In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depend on the size of the matrix. The value of this polynomial, ...

of this matrix (the

square root In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or  ⋅ ) is . For example, 4 and −4 are square roots of 16, because . E ...

of its

determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...

) gives the number of perfect matchings. Each perfect matching contributes

\pm 1

to the Pfaffian regardless of which orientation is used; the choice of a Pfaffian orientation ensures that these contributions all have the same sign as each other, so that none of them cancel. This result stands in contrast to the much higher computational complexity of counting matchings in arbitrary graphs.

Pfaffian graphs

A graph is said to be Pfaffian if it has a Pfaffian orientation. Every

is Pfaffian. An orientation in which each face of a planar graph has an odd number of clockwise-oriented edges is automatically Pfaffian. Such an orientation can be found by starting with an arbitrary orientation of a

spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...

of the graph. The remaining edges, not in this tree, form a spanning tree of the

dual graph In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loop ...

, and their orientations can be chosen according to a bottom-up traversal of the dual spanning tree in order to ensure that each face of the original graph has an odd number of clockwise edges. More generally, every

K_

-minor-free graph has a Pfaffian orientation. These are the graphs that do not have the

K_

(which is not Pfaffian) as a

. By

Wagner's theorem In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither ''K''5 (the complete graph on fi ...

, the

K_

-minor-free graphs are formed by gluing together copies of planar graphs and the

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

K_5

along shared edges. The same gluing structure can be used to obtain a Pfaffian orientation for these graphs. Along with

K_

, there are infinitely many minimal non-Pfaffian graphs. For

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

s, it is possible to determine whether a Pfaffian orientation exists, and if so find one, in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

References

{{reflist, refs= {{citation , last = Kasteleyn , first = P. W. , authorlink = Pieter Kasteleyn , contribution = Graph theory and crystal physics , mr = 0253689 , pages = 43–110 , publisher = Academic Press , location = London , title = Graph Theory and Theoretical Physics , year = 1967 {{citation , last = Little , first = Charles H. C. , journal = Combinatorial Mathematics (Proc. Second Australian Conf., Univ. Melbourne, Melbourne, 1973) , mr = 0382062 , pages = 63–72 , series = Lecture Notes in Mathematics , volume = 403 , publisher = Springer, Berlin , title = An extension of Kasteleyn's method of enumerating the 1-factors of planar graphs , year = 1974 {{citation , last1 = Norine , first1 = Serguei , last2 = Thomas , first2 = Robin , author2-link = Robin Thomas (mathematician) , doi = 10.1016/j.jctb.2007.12.005 , issue = 5 , journal = Journal of Combinatorial Theory , mr = 2442595 , pages = 1038–1055 , series = Series B , title = Minimally non-Pfaffian graphs , volume = 98 , year = 2008, doi-access = free {{citation , last1 = Robertson , first1 = Neil , author1-link = Neil Robertson (mathematician) , last2 = Seymour , first2 = P. D. , author2-link = Paul Seymour (mathematician) , last3 = Thomas , first3 = Robin , author3-link = Robin Thomas (mathematician) , doi = 10.2307/121059 , issue = 3 , journal = Annals of Mathematics , mr = 1740989 , pages = 929–975 , series = Second Series , title = Permanents, Pfaffian orientations, and even directed circuits , volume = 150 , year = 1999, jstor = 121059 , arxiv = math/9911268 {{citation , last = Thomas , first = Robin , authorlink = Robin Thomas (mathematician) , contribution = A survey of Pfaffian orientations of graphs , contribution-url = http://people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf , doi = 10.4171/022-3/47 , mr = 2275714 , pages = 963–984 , publisher = Eur. Math. Soc. , location = Zürich , title = International Congress of Mathematicians. Vol. III , year = 2006 Graph theory objects Matching (graph theory)